To improve user experience, many modern navigation and/or other location-based systems (e.g., embedded systems such as in-vehicle navigation systems, as well as standalone systems such as personal navigation devices and/or mobile devices running navigation applications) provide for voice-based interactions. For example, a voice destination entry (VDE) system is able to configure the destination of the navigation system via a speech interface. However, implementing automatic speech recognition (ASR) for the speech interface can be a significant technical challenge particularly in embedded and portable systems where available resources (e.g., memory, processing power, network bandwidth, etc.) can be limited. For example, having a larger number of valid utterances to provide for more natural voice interaction also means dedicating more system memory to a larger speech decoding graph (e.g., a graph for converting utterances in a voice input signal into geographic information such as a navigation destination). In the context of geographic information, the global speech decoding graph can potentially be larger in size than a device (e.g., an embedded or mobile device) can fit. Accordingly, service providers and device manufacturers face significant technical challenges to enabling more natural speech interactions possible from larger speech decoding graphs, particularly in resource-constrained devices.